package org.example.algorithm.dichotomy;

//高德面试题
//实现一个函数, 完成 开根号 的操作, 方法签名如下.
//double sqrt(int v, double t)
//要求:
//1. 不能调用系统库函数, 诸如 Math.sqrt(v) 之类的;
//2. 假设计算出的结果为 r, 要求满足如下条件 |r−v|≤t, 其中, v 是真实的值, t 为给定的一个误差, 例如0.1等. 千万别被这个不等式吓住, 其实就是希望你计算出的答案 r 要在给定的误差范围内. 举个例子, 我调用你的接口 sqrt(9, 0.21) 返回值属于 [2.79, 3.21] 这个区间的任意一个都满足条件. 因为 9=3, 对于任意的 r∈[2.79,3.21], 都满足 |r−3|≤0.21.
public class MySqrtReturnDoubleSolution {
    public static void main(String[] args) {
        MySqrtReturnDoubleSolution solution = new MySqrtReturnDoubleSolution();
        double ans = solution.sqrt(17, 0.1);
        System.out.println(ans);
    }

    public double sqrt(int v, double t) {
        if (v == 0 || v == 1) {
            return v;
        }
        if (v < 0) {
            throw new RuntimeException("参数错误");
        }
        double left = 0;
        double right = v;
        while (left <= right) {
            double middle = (left + right) / 2.0;
            double temp = middle * middle;
            if (temp == v) {
                return middle;
            } else if (temp > v) {
                right = middle - t;
            } else {
                left = middle + t;
            }
        }
        double ans = 0;
        if (Math.abs(left - t) >= Math.abs(right-t)) {
            ans = right;
        } else {
            ans = left;
        }
        return ans;
    }
}
